7.2 冲突处理方法：链地址法与开放寻址法

哈希表是一种高效的数据结构，用于快速查找、插入和删除数据。然而，哈希表的一个重要问题是哈希冲突，即多个键映射到同一个索引位置。

当出现冲突时，我们需要采取适当的方法来处理冲突。

本节将介绍两种常见的哈希冲突处理方法：链地址法和开放寻址法，并展示如何在Go语言中实现这两种方法。

本节代码存放目录为 lesson16

链地址法

链地址法是一种常用的哈希冲突解决方案。当多个键映射到同一个索引时，将它们存储在一个链表中，所有有相同哈希值的元素都在同一个链表中。

这其实在上一节的代码中我们已经实现了，简单来说就是：每一个索引位置除了存储本身的键值对外，还会存储一个链表，当出现冲突时就将后续的数据存储到链表中。

链地址法的结构如下所示：

• 哈希表的每个索引 对应的是一个链表。

• 每个链表节点 保存的是一个键值对。

• 当发生冲突时，新元素会追加到链表的末尾。

链地址法示意如下所示：

哈希表：

索引    0  1  2  3  4  5  6  7  8  9
存储    -  -  A  -  B  -  -  -  -  -
             |
             C

- A 和 C 发生了哈希冲突，存储在同一个链表中

- B 存储在没有冲突的索引 4

在上面的示例中，A 和 C 都被映射到了索引 2，因此 A 和 C 通过链表存储在该索引位置。访问元素时，只需要遍历该链表即可找到对应的键值对。

开放寻址法

开放寻址法是另一种冲突解决方法，当发生哈希冲突时，寻找下一个可用的空闲位置存储冲突的元素，而不是将冲突元素存储在链表中。

简单来说就是：如果当前位置不能存储了，那么就重新找一个可以存储的位置存储。

开放寻址法的结构如下所示：

• 当发生冲突时，通过线性探测或其他方式寻找下一个可用的存储位置。

• 所有元素 都存储在哈希表的数组中，不需要额外的链表。

开放寻址法的探测方式如下所示：

• 线性探测：每次冲突时，向前移动一定的步长（如 1）寻找空闲位置。

• 二次探测：移动的步长随着冲突次数呈二次递增。

• 双重哈希探测：使用两个哈希函数，发生冲突时使用第二个哈希函数计算新位置。

开放寻址法示意如下所示：

哈希表：

索引    0  1  2  3  4  5  6  7  8  9
存储    -  -  A  -  B  C  -  -  -  -

- A、B 正常存储，C 发生了冲突，存储在 5

在上面的示例中，C 本应存储在索引 2，但是 A 已经占据了该位置，因此 C 通过线性探测存储在了索引 5。

总的来说就是：开放寻址法一直会存储在哈希表中，不会在同一个位置存储多个数据，这种方式可以保证结构的统一性，但是如果冲突过多的话，在查找的时候还是会增加一定的压力。

Go 语言实现开放寻址法（线性探测）

实现代码如下所示：

// HashTable 定义哈希表结构
type HashTable struct {
    table []string
    size  int
}

// NewHashTable 创建一个哈希表
func NewHashTable(size int) *HashTable {
    return &HashTable{
        table: make([]string, size),
        size:  size,
    }
}

// Hash 函数计算哈希值
func (h *HashTable) Hash(key string) int {
    hash := 0
    for _, char := range key {
        hash += int(char)
    }
    return hash % h.size
}

// Put 插入键值对到哈希表
func (h *HashTable) Put(key string, value string) {
    index := h.Hash(key)

    // 如果发生冲突，进行线性探测
    for h.table[index] != "" {
        index = (index + 1) % h.size  // 移动到下一个位置
    }

    h.table[index] = value
}

// Get 根据键查找值
func (h *HashTable) Get(key string) (string, bool) {
    index := h.Hash(key)

    // 线性探测查找值
    for h.table[index] != "" {
        return h.table[index], true
    }
    return "", false
}

func main() {
    // 创建哈希表
    hashTable := NewHashTable(10)

    // 插入键值对
    hashTable.Put("A", "Apple")
    hashTable.Put("B", "Banana")
    hashTable.Put("C", "Cherry")

    // 查找键值对
    value, found := hashTable.Get("B")
    if found {
        fmt.Println("Key B:", value)  // 输出 Key B: Banana
    } else {
        fmt.Println("Key B not found")
    }
}

在上面的代码中我们通过index的重新计算将数据存储到下一个可用位置上。

小结

本节我们讲解了链地址法与开放寻址法，目的都是解决哈希冲突，链地址法与开放寻址法对比如下：

• 链地址法：在哈希表发生冲突时，使用链表存储冲突的元素，适合负载较高的场景。

• 开放寻址法：通过探测寻找空闲位置存储冲突元素，适合负载较低、空间较大的场景。

这两种方法各有优劣，实际应用中会根据场景选择合适的冲突处理方法。